package com.zdb.datastructures.sort;

import com.zdb.datastructures.utils.MockDataUtils;
import com.zdb.datastructures.utils.TimeUtils;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
//        int[] arr = {4,6,8,5,9,-1,90,89,56,-999};
        int[] arr = MockDataUtils.mock80000IntArr();
        TimeUtils.printNowStr();
        heapSort(arr);
        TimeUtils.printNowStr();
    }

    /**
     * 堆排序，升序
     * 1. 先将数组转成一个大顶堆的顺序
     * 2. 将转换后的数组的第一个元素和最后一个元素对换
     * 3. 再将去除最后一位的arr 转成大顶堆，再对换，以此循环到arr的长度为1
     * @param arr
     */
    public static void heapSort(int[] arr) {

        /**
        // 分步完成
        adjustHeap(arr, 1, arr.length);
        // 4 9 8 5 6
        System.out.println("第一次：" + Arrays.toString(arr));

        adjustHeap(arr, 0, arr.length);
        // 9 6 8 5 4
        System.out.println("第二次：" + Arrays.toString(arr));
         */

        int tmp = 0;
        // 最终代码
        for(int i=arr.length/2 -1; i>=0; i--) {
            adjustHeap(arr, i, arr.length);
        }

//        System.out.println("对数组进行大顶堆排序后：" + Arrays.toString(arr));

        // 交换
        for(int j=arr.length -1; j>0; j--) {
            tmp = arr[j];
            arr[j] = arr[0];
            arr[0] = tmp;
//            for(int i=j/2 -1; i>=0; i--) {
//                adjustHeap(arr, i, arr.length);
//            }
            adjustHeap(arr, 0, j);
        }
//        System.out.println("堆排序结果：" + Arrays.toString(arr));
    }

    /**
     * 功能：完成将以i对应的非叶子节点的树调整成大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子节点的数组中索引
     * @param length 表示对arr中多少个元素进行调整，length是在逐渐减少
     */
    public static void adjustHeap(int arr[], int i, int length) {
        // 先取出当前元素的值，保存在临时变量
        int temp = arr[i];
        // 开始调整
        // 说明
        // 1. k=i*2 +1, k是i节点的左子节点
        for(int k=2*i+1; k<length; k=2*k+1) {
            // 说明左子节点的值小于右子节点的值
            if(k+1 < length && arr[k] < arr[k+1]) {
                // 将k指向右子节点
                k++;
            }
            // 如果子节点大于父节点
            if(arr[k] > temp) {
                // 把较大的值赋给当前节点
                arr[i] = arr[k];
                // i指向k，继续循环比较
                i = k;
            } else {
                break;
            }
            // 当for循环结束后，我们已经将以i为父节点的树的最大值放在了最顶(局部)
            // 将temp值放到调整后的位置
            arr[i] = temp;
        }
    }
}
